//============================================================================
// Name        : Cavalo.cpp
// Author      : MC
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>

using namespace std;

const int maxSize = 8;

int h[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int v[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int movimentosTotal;


bool tenta(unsigned int i, int x, int y, bool &qq, int pp[maxSize][maxSize]){
	int xn, yn, m;
	bool q;
	m = 0;
	q = false;
	do{
		//tenta movimento
		xn = x + h[m];
		yn = y + v[m];
		m++;
		// verifica se esta dentro do tabuleiro
		if( (xn < 0) || (xn >= maxSize) || (yn < 0) || (yn >= maxSize) ) continue;
		//verifica se livre
		if(pp[xn][yn] == 0){
			//ocupa
			pp[xn][yn] = i;
			if( i < maxSize*maxSize){
				tenta(i+1, xn, yn, q, pp);
				if(!q) pp[xn][yn] = 0;
			}
			else q = true;
		}
	}while(m < 8 && !q); //tenta ate achar solucao
	qq = q;
}



//Passeio do cavalo
int main() {
	int pp[maxSize][maxSize];	
	bool q;
	int posX, posY;
	cout << endl << endl;
	
	posX = 0;
	posY = 0;
	movimentosTotal = 0;
	
	for(int _x=0; _x < maxSize; _x++ ) for(int _y=0; _y < maxSize; _y++ ) pp[_x][_y] = 0;
	
	//primeiro passo
	pp[0][0] = 1;
	tenta(2,0,0,q, pp);

	if(q) cout << "Achou... " << endl;
	else  cout << "Nao achou... " << endl;
	cout << endl;
	
	for(int _x=0; _x < maxSize; _x++ ){
		for(int _y=0; _y < maxSize; _y++ ) cout << "\t" << pp[_x][_y];
		cout << endl;
	}
	return 0;
}
